modeltheoryfandomcom-20200213-history
Compactness
The Compactness Theorem states that if T'' is a collection of first-order statements and every finite subset of ''T is consistent, then T'' is itself consistent. A set of statements is ''consistent if it has a model. By abuse of terminology, the following related fact is also frequently referred to as "compactness." Let M'' be a \kappa -saturated model, D \subset M^n be a definable set, and \Sigma be a collection of definable subsets of M^n , with \Sigma of size less than \kappa . If \Sigma covers ''D, then some finite subset of \Sigma covers D''. This fact follows from the definition of \kappa -saturation. Compactness is used to prove the existence of \kappa -saturated models, however. Common Corollaries and Uses of Compactness The compactness theorem has a number of commonly-used corollaries. These corollaries are often used implicitly in proofs, and explained only as "compactness." '''Lemma:' Let M'' be a model, and \Sigma(x) be a consistent partial type over ''M. Then there is an elementary extension M' \succeq M in which \Sigma(x) is realized. Proof: Apply the Compactness Theorem to the union of the elementary diagram of M'' and the statements \Sigma© , where c is a new constant symbol. QED '''Lemma:' Let T'' be a theory. Let \phi(x) be a formula, and let \{\psi_i(x) : i \in I\} be a collection of formulas. Suppose that in every model ''M of T'', we have : \phi(M) \subseteq \bigcup_{i \in I} \psi_i(M) . Then there is a finite subset I_0 \subset I such that in every model ''M of T'', : \phi(M) \subseteq \bigcup_{i \in I_0} \psi_i(M) . '''Proof:' Apply compactness to the union of T'' and the statements : \{ \phi© \} \cup \{ \neg \psi_i© : i \in I\} where c is a new constant symbol. By assumption, this collection of statements is inconsistent, so by compactness, some finite subset is inconsistent. This yields I_0 . QED '''Lemma:' Let T'' be a theory, and \phi(x) be a formula. Suppose that in every model ''M of T'', the set \phi(M) is finite. Then there is a number ''n such that |\phi(M)| < n for every model M''. '''Proof:' Apply compactness to the union of T'' and the set of sentences \psi_n asserting for each ''n that at least n'' elements of the model satisfy \phi . By assumption, this is inconsistent. Consequently, there is some ''n such that \psi_n is inconsistent with T''. This means exactly that |\phi(M)| < n in every model of ''T. QED The analogous statement in saturated models is the following: Lemma: Let M'' be a \aleph_1 -saturated model. Suppose that \phi(x;y) is a formula such that for every b \in M , the set \phi(M;b) is finite. Then there is a uniform bound ''n on the size of \phi(M;b) . Other important and prototypical applications of compactness include the following: * The Upwards Löwenheim-Skolem Theorem * The existence of indiscernible sequences * The existence of \kappa -saturated models * The equivalence between the existence of Skolem functions and the property that every substructure is an elementary substructure. * The equivalence between elimination of imaginaries and the interdefinability of every imaginary element with a real element. * The statement that if every substructure of a model of T'' is a model of ''T, then T'' is equivalent to a set of universal statements. Interpretation as Compactness of Stone Space Let ''S denote the space of all complete theories (in some fixed first-order language). For each sentence \phi , let : \phi = \{ T \in S | \phi \in T \} There is a natural topology on S'' in which the sets of the form \phi are the basic open (and basic closed) subsets. The compactness theorem says exactly that ''S is compact with this topology. Proofs of Compactness Compactness follows easily from some forms of Gödel's Completeness Theorem. Specifically, a theory T is inconsistent if and only if \exists x : x \ne x holds in all models of T . By the Completeness Theorem, this holds if and only if \exists x : x \neq x can be proven from T . But proofs are finitary, so any proof must take only finitely many steps, and must use only a finite subset of T . In particular, if T proves \exists x : x \neq x , then so does some finite subset T_0 \subset T . So if T is inconsistent, so is a finite subset. Compactness can alternatively be proven from Łoś's Theorem. Proof: Let T'' be a collection of statements, with every finite subset of ''T being consistent. Let X'' be the set of all finite of ''T. For each finite subset S \subset T , let : X_S = \{ T' \in X | S \subset T'\} Note that X_S \cap X_T = X_{S \cup T} and that X_S \ne \emptyset for any S''. It follows that any finite intersection of X_S 's is non-empty. Therefore we can find an ultrafilter \mathcal{U} on ''X such that X_S \in \mathcal{U} for every S''. In other words, for each ''S, \mathcal{U} thinks that "most" elements of X'' contain ''S. For each finite subset S'' of ''T, we can find a model M_S of S'', by assumption. Consider the ultraproduct : M = \prod_{S \in X} M_S / \mathcal{U} We claim that ''M is the desired model of T''. Let \phi be a formula in ''T. Then : M_S \models \phi for every S \ni \phi , or equivalently, for every S \in X_{\{\phi\}} . But : X_{\{\phi\}} \in \mathcal{U} . Consequently, the set of S'' such that M_S \models \phi is "large" with respect to the ultrafilter \mathcal{U} . By Łoś's Theorem, \phi holds in the ultraproduct ''M. QED